home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 3: Developer Tools / Linux Cubed Series 3 - Developer Tools.iso / devel / lang / lisp / glisp / glisp.000 / GLISP.UNIX.TAR / closunix / closhash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-04-03  |  3.8 KB  |  172 lines
  1. /*                 GRAPHIC LISP            */
  2. /*        Scritto nel 1991-94 da Zoia Andrea Michele     */
  3. /*        Via Pergola #1 Tirano (SO) Tel. 0342-704210    */
  4. /* file closhash.c */
  5.  
  6. #include "clos.h"
  7.  
  8. /* gestione della HashTable  */
  9.  
  10. node   *HashTable=NULL;
  11. hash_t MaxHash;
  12. hash_t HashAllocated;
  13. char  Hash_buf1[MAX_ID_LENGHT+1];
  14.  
  15. hash_t hash();
  16.  
  17.  
  18. hash_t hash(s)
  19. char *s;
  20. {
  21.  /* NOTA: si suppone che sizeof(unsigned long int)=4byte(32 bit) */
  22.  unsigned int i;
  23.  unsigned long ret;
  24.  
  25.  ret=0L;
  26.  for(i=0;s[i];i++){
  27.     ret+=((unsigned long int)((unsigned char)s[i]))<<((i%16)<<1);
  28.  }
  29.  return (hash_t)ret%MaxHash;    /* tra 0 e maxhash-1 */
  30. }
  31.  
  32. node    hash_search(s,nh)
  33. char *s;
  34. hash_t *nh;
  35. {
  36. /*
  37.    se trova *s ritorna il nodo col nome corrispondente e
  38.         nh viene settato al suo hash
  39.    se non lo trova ritorna VOID e nh settato all'hash libero
  40.    se hashtable e' piena salta a jumpbuf stampando l'errore HASHFULL
  41.    NON bisogna chiamarla con s=NULL
  42. */
  43.  int    found_flag;
  44.  hash_t    found_hash;
  45.  hash_t current;
  46.  hash_t first;
  47.  
  48.  current=first=hash(s);
  49.  found_flag=FALSE;
  50.  for(;;){
  51.    if(HashTable[(unsigned)current]==VOID){
  52.      /* p punta ad un hash vuoto */
  53.      /* vuol dire che s non e' stata tovata nella hastable */
  54.      /* allora si guarda found_flag */
  55.      /* se e' TRUE allora found_flag contiene il primo hash cancellato */
  56.      /* che approssima meglio l'hash effettivo di s */
  57.      /* se e' FALSE allora l'hash migliore e' proprio current */
  58.  
  59.      *nh=found_flag?found_hash:current;
  60.  
  61.      /* si ritorna VOID ad per indicare che la stringa s non e' stata trovata */
  62.      /* ma che potrebbe essere messa nella posizione *nh */
  63.  
  64.      return VOID;
  65.    }
  66.    if(HashTable[(unsigned)current]==DELETED){
  67.      /* se current e' cancellato allora ci si ricorda di questo hash */
  68.      /* (se e' il primo trovato) dato che e' il migliore per la stringa s */
  69.      if(!found_flag){
  70.        found_hash=current;
  71.        found_flag=TRUE;
  72.      }
  73.    }else{
  74.      /* current punta ad un hash occupato */
  75.  
  76.      if(!strcmp(string_get(NAME(HashTable[(unsigned)current]),Hash_buf1),s)){
  77.        /* ok rappresenta proprio il nodo di nome s */
  78.        /* la procedura allora ritorna il nodo di nome s */
  79.        /* e setta nh al valore dell'hash */
  80.  
  81.        *nh=current;
  82.        return (node)HashTable[(unsigned)current];
  83.      }
  84.    }
  85.    /* si incrementa circolarmente current */
  86.    current=((++current)<MaxHash)?current:0;
  87.  
  88.    /* se current e' tornato ad essere uguale a first allora si e' */
  89.    /* passata tutta la hashtable senza trovare la stringa s */
  90.    if(current==first){
  91.      if(found_flag){
  92.        /* pero' l'hash cancellato lo si e' trovato */
  93.        *nh=found_hash;
  94.        return VOID;
  95.      }
  96.      /* l'hash table e' piena */
  97.      error(E_HASHFULL,ERR_TCRIT|ERR_MERROR|ERR_PVOID,NULL);
  98.    }
  99.  }/* for(;;) */
  100. }
  101.  
  102. void  hash_put(n,h)
  103. node n;
  104. hash_t h;
  105. {
  106.  /* inserisce il nodo n nella posizione h */
  107.  HashTable[(unsigned)h]=n;
  108.  HashAllocated++;
  109. }
  110.  
  111. void hash_del(h)
  112. hash_t h;
  113. {
  114.  /* rimuove la posizione h */
  115.  HashTable[(unsigned)h]=DELETED;
  116.  HashAllocated--;
  117. }
  118.  
  119. int hash_malloc(h)
  120. lsiz_t h;
  121. {
  122.  /* alloca la memoria per la hashtable */
  123.  unsigned long int i;
  124.  
  125.  if(h*sizeof(node)>0xffffL) return ERROR;
  126.  
  127.  if((HashTable=(node *)malloc((unsigned)h*(unsigned)sizeof(node)))==NULL){
  128.     HashTable=NULL;
  129.     MaxHash=0L;
  130.     return ERROR;
  131.  }
  132.  for(i=0;i<h;i++){
  133.     HashTable[(unsigned)i]=VOID;
  134.  }
  135.  MaxHash=(hash_t)h;
  136.  HashAllocated=(hash_t)0;
  137.  return OK;
  138. }
  139.  
  140. void hash_free()
  141. {
  142.  if(HashTable)
  143.    free(HashTable);
  144.  HashTable=NULL;
  145. }
  146.  
  147.  
  148.  
  149. void hash_stat()
  150. {
  151.  /* stampa la hashtable su stderr */
  152.  /* '-' hash vuoto ,'#' Allocato  '=' cancellato */
  153.  
  154.  hash_t counter;
  155.  
  156.  for(counter=0;counter<MaxHash;counter++){
  157.    if(HashTable[(unsigned)counter]==VOID){
  158.        lisp_print_string(".",stderr);
  159.    }else{
  160.      if(HashTable[(unsigned)counter]==DELETED){
  161.        lisp_print_string("*",stderr);
  162.      }else{
  163.        lisp_print_string("#",stderr);
  164.      }
  165.   }    
  166.  }
  167.  lisp_print_string("\n",stderr);
  168. }  
  169.  
  170.  
  171.  
  172.